/**
 * @param {number[]} parent
 */
 var LockingTree = function(parent) {
  this.parent = parent
  this.lockMap = new Map()
  const n = parent.length
  this.lockCondition = new Array(n).fill(false)
  const childrenMap = new Map()
  for(let i = 0; i<n; i++){
    if(!childrenMap.has(parent[i])){
      childrenMap.set(parent[i],[])
    }
    childrenMap.get(parent[i]).push(i)
  }
  this.childrenMap = childrenMap
};

/** 
 * @param {number} num 
 * @param {number} user
 * @return {boolean}
 */
LockingTree.prototype.lock = function(num, user) {
  const { parent, lockMap, lockCondition } = this
  if(lockCondition[num]){
    return false
  }
  lockMap.set(num, user)
  lockCondition[num] = true
  return true
};

/** 
 * @param {number} num 
 * @param {number} user
 * @return {boolean}
 */
LockingTree.prototype.unlock = function(num, user) {
  const { parent, lockMap, lockCondition } = this
  if(lockCondition[num] && lockMap.has(num) && lockMap.get(num) === user){
    lockMap.delete(num)
    lockCondition[num] = false
    return true
  }
  return false
};



function checkParent (num, root, parent, lockCondition) {
  if(root === -1){
    return false
  }
  if(lockCondition[root]){
    return true
  }
  return checkParent(num, parent[root], parent, lockCondition)
}

function checkChild (num, lockCondition, childrenMap) {
  const queue = [num]
  while(queue.length){
    for(let i = 0, len = queue.length; i<len; i++){
      const now = queue.shift()
      if(now !== num && lockCondition[now]){
        return true
      }
      if(childrenMap.has(now)){
        for(const next of childrenMap.get(now)){
          queue.push(next)
        }
      }
    }
  }
  return false
}

function unlockAll (num, user, lockMap, lockCondition, childrenMap) {
  const queue = [num]
  while(queue.length){
    for(let i = 0, len = queue.length; i<len; i++){
      const now = queue.shift()
      if(lockCondition[now]){
        lockMap.delete(num)
        lockCondition[num] = false
      }
      if(childrenMap.has(now)){
        for(const next of childrenMap.get(now)){
          queue.push(next)
        }
      }
    }
  }
  lockMap.set(num, user)
  lockCondition[num] = true
}

/** 
 * @param {number} num 
 * @param {number} user
 * @return {boolean}
 */
LockingTree.prototype.upgrade = function(num, user) {
  const { parent, lockMap, lockCondition, childrenMap } = this
  console.log("parent", checkParent(num, num, parent, lockCondition))
  console.log("child", checkChild(num, lockCondition, childrenMap))
  if(lockCondition[num] || checkParent(num, num, parent, lockCondition) || checkChild(num, lockCondition, childrenMap)){
    return false
  }
  unlockAll(num, user, lockMap, lockCondition, childrenMap)
  return true
};

/**
 * Your LockingTree object will be instantiated and called as such:
 * var obj = new LockingTree(parent)
 * var param_1 = obj.lock(num,user)
 * var param_2 = obj.unlock(num,user)
 * var param_3 = obj.upgrade(num,user)
 */